665. Non-decreasing Array
Medium

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

 

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

 

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • -105 <= nums[i] <= 105
Accepted
153.5K
Submissions
734.6K
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.61 (18 votes)

Premium

Solution


Approach: Greedy

Intuition

The one thing that we should focus on here is the fact that the problem description says non-decreasing, which is just another way of saying increasing. In this case, it means the next element must always be greater than or equal to the current element. Thus, in an array, the item on the left must be less than or equal to the item on the right. Since we can only rectify a single violation of this rule, if more than one violation exists, it is impossible to make the array non-decreasing.

The first time we encounter such a violation i.e. nums[i - 1] > nums[i], we make a change. You don't actually have to make a change because the question doesn't ask us to give the final array in order, it just asks if it could become non-decreasing. Then, we move on with the rest of the array, and continue to check for other violations. If it ever so happens that the rule gets violated again, we return false since this would be the second violation of the rule. If we don't find a second violation, we can return true since rectifying the first violation made our array non-decreasing.

Whenever we encounter a violation at a particular index i, we need to check what modification we can make to make the array sorted. Let's see this scenario using an example.

Single violation

Figure 1. A violation in the sorted array.

In the example above, we consider the numbers 4, 5, 3 for deciding on how to fix the violation or. In this case, the correct modification is to change the number 3 to 5. If we change 5 to 3, then we won't be fixing the violation because the resulting array would be 3, 4, 3, 3, 6, 8.

Single violation modification

Figure 2. Rectifying a single violation leading to sorted array.

The basic decision making process for fixing a violation is listed below. Without considering the number at the index i - 2, we won't be able to choose between updating nums[i] or nums[i - 1]. The modification has to fit in with the sorted nature of the array.

if nums[i - 2] > nums[i] then
    nums[i] = nums[i - 1]
else
    nums[i - 1] = nums[i]

Once we make the modification, we expect that the rest of the array will be sorted. If that is not the case, then we return false from our function. Some arrays will have violations in different places e.g. a 10 element array where nums[4] > nums[5] and also nums[8] > nums[9]. This array cannot be sorted by only fixing the violation at nums[5].

Additionally, it is possible that a modification in the array leads to another violation that did not exist before. Let's consider an example where this can happen.

Additional violation introduced

Figure 3. Rectifying a single violation introduces a new violation.

Algorithm

  1. We iterate over the array until we reach the end of the array or find a violation.
  2. If we reach the end of the array, we know it is sorted and we return true.
  3. Otherwise, we found a violation. We consider the nums[i - 2] to fix the violation.
    • If the violation is at the index 1, we won't have a nums[i - 2] available. In that case we simply set nums[i - 1] equal to nums[i].
    • Otherwise, we check if nums[i - 2] <= nums[i] in which case we set nums[i - 1] equal to nums[i].
    • Finaly, if nums[i - 2] > nums[i], then we set nums[i] equal to nums[i - 1].
  4. Once we make the modification, we simply iterate over the remaining array. If we find another violation, we return false. Otherwise, we return true once the iteration is complete.

Implementation

Complexity Analysis

  • Time Complexity: O(n)O(n) considering there are nn elements in the array and we process each element at most once.

  • Space Complexity: O(1)O(1) since we don't use any additional space apart from a couple of variables for executing this algorithm.

Report Article Issue

Comments: 10
dana-n's avatar
Read More

Why modify the input array? Yes, is a peeve of mine :) We are not adding value, i.e. sorting, so this code is destructive. Passing in the same array twice could yield different results (i.e. non-deterministic).

Instead, try something like this:

public bool CheckPossibility(int[] nums) {
    int badIdx = -1;
    for (int i = 0; i < nums.Length - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            if (badIdx == -1) {
                badIdx = i;
            }
            else {
                return false;
            }
        }
    }
    if (badIdx <= 0 || badIdx == nums.Length - 2) {
        return true;
    }
    else {
        return nums[badIdx - 1] <= nums[badIdx + 1] || nums[badIdx] <= nums[badIdx + 2];
    }
}

4
Reply
Share
Report
AsahiOcean's avatar
Read More

Hi, dudes! How's tricks?

class Solution {
    func checkPossibility(_ nums: [Int]) -> Bool {
        guard nums.count > 2 else { return true }
        var modify = 0, n = nums.count - 1
        while n != 0 {
            if nums[n] < nums[n-1] {
                modify += 1
                if n > 1,
                   n < nums.count - 1,
                   nums[n+1] < nums[n-1],
                   nums[n-2] > nums[n] { return false }
            }
            if modify > 1 { return false }
            n -= 1
        }
        return true
    }
}
import XCTest

// Executed 2 tests, with 0 failures (0 unexpected) in 0.004 (0.006) seconds

class Tests: XCTestCase {
    private let s = Solution()
    func testExample1() {
        XCTAssertTrue(s.checkPossibility([4,2,3])) // success
    }
    func testExample2() {
        XCTAssertFalse(s.checkPossibility([4,2,1])) // success
    }
}

Tests.defaultTestSuite.run()

4
Reply
Share
Report
descartes131's avatar
Read More

This solution is simple and easy to understand with visualized diagrams. Just one more thing to consider is that it's always better solution not to modify input.

here is my solution not to modify input. It just checks whether it's possible to make local non decreasing state and then if it is not possible, just return false.

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int len = nums.size();
        bool modified = false;
        for (int i=0; i < len-1; i++) {
            if (nums[i] > nums[i+1]) {
                if (modified) {
                    return false;
                }
                if (i-1 < 0 || nums[i-1] <= nums[i+1]) {
                    // in this case, you can change nums[i] = x (nums[i-1] <= x <= nums[i+1])
                } else if (i + 2 >= len || nums[i] <= nums[i+2]) {
                    // in this case, you can change nums[i+1] = x (nums[i] <= x <= nums[i+2])
                } else {
                    // if it's not the both of them, it's not possible to make sorted state with one modification
                    return false;
                }
                modified = true;
            }
        }
        return true;
    }
};

4
Reply
Share
Report
neal99's avatar
Read More

Follow up: what if you can change at most k elements?

3
Show 5 replies
Reply
Share
Report
kanishkgupta2000's avatar
Read More

Another way to look at this is this, if the longest increasing subsequence is greater than equal to n-1, then return true, else return false, O(nlogn) though, just hit me hence tried, passing all test cases, though obviously the solution approach is better.

1
Show 4 replies
Reply
Share
Report
Neoteny's avatar
Read More

Wow, this question was trickier than i thought at the beginning.

0
Reply
Share
Report
wooyaro's avatar
Read More

This is medium? I have been staring into space with this problem :(

0
Show 1 reply
Reply
Share
Report
bharatham's avatar
Read More

How would you rate this? Pop the bad one and see if it's sorted.

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        if all(nums[i] <= nums[i+1] for i in range(len(nums)-1)):
            return True
        for i in range(0,len(nums)):
            o = list(nums)
            o.pop(i)
            if all(o[x] <= o[x+1] for x in range(len(o)-1)):
                return True
        return False

0
Show 1 reply
Reply
Share
Report
yi64's avatar
Read More

We can insert a minimum value to remove i < 2 check in if i < 2 or nums[i - 2] <= nums[i]:, here is the code in Python3,

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        nums.insert(0, -10**5)
        hit = False
        for i in range(2, len(nums)):
            if nums[i-1] > nums[i]:
                if hit:
                    return False
                hit = True
                
                if nums[i-2] > nums[i]:
                    nums[i] = nums[i-1]
                else:
                    nums[i-1] = nums[i-2]
        return True

0
Reply
Share
Report
mehakwaliaC's avatar
Read More

Here is a straightforward approach O(n) using stack.

bool checkPossibility(vector<int>& nums) {
        stack<int> stk;
        bool modified=false;
        stk.push(INT_MIN); // if any changes at num[0] are required
        stk.push(nums[0]);
        for (int i=1; i<nums.size(); i++){
            if (nums[i]>=nums[i-1]){
				stk.push(nums[i]); 
				 }
            else{
                if (modified) return false;// already modified a value?
                modified=true;
                //either (a) make num[i] to be equal to nums[i-1]
                //or (b) make the num[i-1] to be the least possible value possible for it
				// we could only do one of the above to make the array right
                int last=stk.top();
                stk.pop();
                int largestOnStack=stk.top();
                if (largestOnStack>nums[i]){nums[i]= last;} // [... 4, 5, 3, ...] we will have to modify 3 to 5
                else
                    last= largestOnStack; // [...3, 5, 4...] we can change 5 to 4 and the array would still be valid!
                stk.push(last);
                stk.push(nums[i]);
            }
        }
        return true;
    }

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/04/2021 19:09Accepted32 ms27 MBcpp
05/04/2021 19:04Wrong AnswerN/AN/Acpp
06/27/2020 14:33Accepted216 ms15 MBpython3
06/27/2020 14:24Wrong AnswerN/AN/Acpp
06/27/2020 14:23Wrong AnswerN/AN/Acpp
/23
Contribute
|||
Saved
Trie
This list is empty.